import java.util.Arrays;

/**
 * @author huu
 * @create 2025-09-07-11:13
 */
public class canJump {
    // 动态规划
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int fast = 0;
        for(int i = 0; i < n; i++){
            if(i > fast) return false;
            fast = Math.max(fast, i + nums[i]);
        }
        return fast >= n-1;
    }

    //跳跃游戏二
    public int jump(int[] nums) {

        //一个数组用来存放跳到当前位置所需的最少次数
        int[] dp = new int[nums.length];
        //初始化dp数组为最大值
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0; i < nums.length; i++){
            int c = nums[i] + i;
            for(int j = i+1; j <= c && j < nums.length; j++){
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
        return dp[nums.length-1];
    }
}

